package com.lw.leetcode.back.b;

import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/11 11:37
 */
public class NearestExit {

    public static void main(String[] args) {
        NearestExit test = new NearestExit();

        // 2
//        char[][] arr = {{'+', '+', '+'}, {'.', '.', '.'}, {'+', '+', '+'}};
//        int[] items = {1, 0};

        // 2
        char[][] arr = {{'+', '.', '.', '+', '.', '+'},
                {'+', '+', '.', '+', '+', '+'},
                {'+', '.', '+', '+', '+', '+'},
                {'.', '.', '+', '+', '+', '+'},
                {'.', '+', '+', '+', '.', '+'},
                {'+', '.', '+', '.', '+', '+'}};
        int[] items = {2, 1};

        int i = test.nearestExit(arr, items);
        System.out.println(i);
    }


    public int nearestExit(char[][] maze, int[] entrance) {
        Set<Integer> a = new HashSet<>();
        Set<Integer> b = new HashSet<>();
        int m = maze.length;
        int n = maze[0].length;
        int step = 1;
        int i = entrance[0];
        int j = entrance[1];
        maze[i][j] = '+';
        i++;
        if (!(i < 0 || i == m) && maze[i][j] == '.') {
            a.add((i << 8) + j);
        }
        i -= 2;
        if (!(i < 0 || i == m) && maze[i][j] == '.') {
            a.add((i << 8) + j);
        }
        i++;
        j++;
        if (!(j < 0 || j == n) && maze[i][j] == '.') {
            a.add((i << 8) + j);
        }
        j -= 2;
        if (!(j < 0 || j == n) && maze[i][j] == '.') {
            a.add((i << 8) + j);
        }
        while (!a.isEmpty()) {
            for (int v : a) {
                int y = v & 127;
                int x = (v - y) >> 8;
                maze[x][y] = '+';
                if (x == 0 || x == m - 1 || y == 0 || y == n - 1) {
                    return step;
                }
                if (maze[x + 1][y] == '.') {
                    b.add(((x + 1) << 8) + y);
                }
                if (maze[x - 1][y] == '.') {
                    b.add(((x - 1) << 8) + y);
                }
                if (maze[x][y - 1] == '.') {
                    b.add(((x) << 8) + y - 1);
                }
                if (maze[x][y + 1] == '.') {
                    b.add(((x) << 8) + y + 1);
                }
            }
            a.clear();
            a.addAll(b);
            b.clear();
            step++;
        }
        return -1;
    }


}
